1. Field of the Invention
Methods consistent with the present invention relate to a clustering method of a wireless sensor network (WSN), and more particularly, to a clustering method of a wireless sensor network to minimize energy consumption.
2. Description of the Prior Art
Nodes of WSNs operate on batteries. Because battery power is limited, it is important to design a WSN which minimizes energy consumption.
A clustering method has been proposed with an aim to minimizing energy consumption in the WSN. According to the proposed clustering method, the WSN is divided into a plurality of clusters, and nodes of each cluster take respective roles.
The nodes of the clusters are classified as a cluster head (CH), a gateway (GW) and an ordinary node (ON) according to given roles. A ON detects the event occurring in a corresponding area, and transmits the information to a CH of the same cluster. A CH performs data aggregation with respect to the data received from ONs. A GW routes among neighboring CHs.
The CH performs data aggregation and the GW performs routing, which means that CHs and GWs consume far more energy than ONs. Accordingly, in order to minimize energy consumption in a WSN, it is very important to minimize the number of CHs and GWs.
Available clustering methods mainly include a least identification (ID) clustering, a linked clustering and a topology discovery(TopDisc).
The least ID clustering is based on the IDs of the nodes. More specifically, all the nodes in the cluster initialization stage transmit to the neighboring nodes within the radio range the advertisement message which contains their ID. After completion of the advertisement message transmission, a node with the lowest ID becomes the CH. Accordingly, a node having a lower ID than the other neighboring nodes announces to the neighboring nodes that it is the CH. Next, the CH transmits a beacon signal to the neighboring nodes. At this time, the neighboring nodes receiving the beacon signal from one CH become ONs, while the neighboring nodes receiving the beacon from two or more CHs become GWs.
The least ID clustering has the advantage of simplicity, but since there are many CHs and GWs, which generally consume large amounts of energy, energy consumption increases in the WSN.
The linked clustering allocates unique slots to the nodes in the order of higher IDs. Accordingly, an IN (initial node) having the higher ID announces that it is CH in the first slot allocated to itself, and transmits a beacon signal to the nodes within radio range. INs receiving the beacon signal become ONs. The other INs, which are not turned into ONs, announce that they are CHs in the respectively allocated slots, and transmit a beacon signal to the INs within the radio range. Nodes receiving the beacon signal from two or more CHs become GWs.
The linked clustering has disadvantages in that synchronization in the entire WSN is required for the allocation of slots, and more particularly, since many CHs and GWs are generated, energy consumption increases.
The TopDisc clustering minimizes the number of CHs and GWs by minimizing the distance between CHs and GWs. This method is based on the assumption that the propagation delay time is in proportion to the physical distance between the nodes. More specifically, a CH broadcasts a TopDisc message to the nodes within radio range, and measures transmission delay time of the response messages received from the respective nodes. The CH considers a node with the longest delay time to be the farthest node, and therefore, designates it as a GW. The GW designates the CH of the neighboring cluster in the same method as explained above. This procedure is applied to the overall WSN.
However, when considering the fading or multi-channel routing in the WSN environment, designating GWs and CHs according to the relative distances between the nodes cannot be accurate. Additionally, when considering that the range of WSN is relatively narrow, which is within several meters, the distance between transmission delays is very minute, and thus, it is somewhat improper to designate GWs and CHs based on the delay time.